這是什麼？

在創造出 Binary Tree 後，思索著能否改善 Search 的速度，經過研究後發現，如果排列節點的方式參考 Binary Search，將能提升搜尋的速度。

好比 Linear Search 的 O(n) 變成 Binary Search 的 O(log n)，運用到 Binary Tree 也是一樣的道理。

關鍵因素

先決條件：輸入的資料沒有重複性。

首先輸入第一個資料作為 root，接著，後續的資料的插入方式為：

1. 如果數值小於 root，那放置在左邊子節點。
2. 如果數值大於 root，那放置在右邊子節點。
3. 到達新節點後：
   1. 如果該節點沒有數值，那放置資料成為新的節點。
   2. 如果有數值，那進行比較，小於前往左邊子節點；大於前往右邊子節點。

依照上面的準則，那成果將會是：

這邊要提醒一下，最棒的情況是，從有排序過的數列內，中間的元素當作 root，接著插入的元素是左半邊與右半邊數列的中間元素，持續找尋中間元素好新增節點。

如果沒有排序的數列隨意新增，那長出來的樹可能偏重右邊或是左邊，這將不利於搜尋，進而讓新增、刪除節點的效率下降。

實作：新增節點 Insertion 與刪除節點 Deletion

• 新增節點來源
• 刪除節點來源

需要注意刪除節點，因為有三種可能，用剛剛上方的 BST 作為範例：

1. 刪除 Leaf，直接刪除節點即可（移除 7）。
   
2. 刪除只有一個子節點的節點，先移除該節點後再將子節點挪到刪除的位置（移除 6）。
   
3. 刪除有兩個子節點的節點，先找尋時適合替代即將被刪除節點的中序接續子（Inorder Successor）節點，接著讓接續子節點取代被刪除的子節點，假如接續子節點本身也有子節點，那要同步找尋適合放置的位置。（移除 11）。
   

比較要注意的是，Inorder Successor 的右子節點不能為 Null。

用 JS 實作

class node {
  /**
   * @param {number} val
   * @param {node} left
   * @param {node} right
   */
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

/**
 * @param {node} root
 * @param {number} val
 */
const deleteNode = (root, val) => {
  if (root === null) {
    return root;
  }

  if (val < root.val) {
    root.left = deleteNode(root.left, val);
  } else if (val > root.val) {
    root.right = deleteNode(root.right, val);
  } else {
    // 找到要刪除的節點

    // 判斷是 Leaf？擁有一個子節點的節點？
    if (root.left == null) {
      return root.right;
    } else if (root.right == null) {
      return root.left;
    }

    // 擁有兩個子節點的節點
    // 製作 Inorder Successor
    root.val = minValue(root.right);
    // 刪除 Inorder Successor
    root.right = deleteNode(root.right, root.val);
  }

  return root;
};

/**
 * @param {node} root
 */
const minValue = (root) => {
  let minValue = root.val;

  while (root.left !== null) {
    minValue = root.left.val;
    root = root.left;
  }

  return minValue;
};

/**
 * @param {node} root
 * @param {number} val
 */
const insertNode = (root, val) => {
  if (root === null) {
    root = new node(val);
    return root;
  }

  if (val < root.val) {
    root.left = insertNode(root.left, val);
  } else if (val > root.val) {
    root.right = insertNode(root.right, val);
  }

  return root;
};

/**
 * @param {node} root
 */
const inorder = (root) => {
  if (root !== null) {
    inorder(root.left);
    console.log(root.val);
    inorder(root.right);
  }
};

let tree = null;
tree = insertNode(tree, 50);
tree = insertNode(tree, 30);
tree = insertNode(tree, 20);
tree = insertNode(tree, 40);
tree = insertNode(tree, 70);
tree = insertNode(tree, 60);
tree = insertNode(tree, 80);

console.log("Inorder traversal of the given tree");
inorder(tree);

console.log("\nDelete 20");
deleteNode(tree, 20);
console.log("Inorder traversal of the modified tree");
inorder(tree);

console.log("\nDelete 30");
deleteNode(tree, 30);
console.log("Inorder traversal of the modified tree");
inorder(tree);

console.log("\nDelete 50");
deleteNode(tree, 50);
console.log("Inorder traversal of the modified tree");
inorder(tree);

用 Java 實作

public class BinarySearchTree {
    static class Node {
        int val;
        Node left, right;

        public Node(int val) {
            this.val = val;
            left = null;
            right = null;
        }
    }

    Node root;

    BinarySearchTree() {
        root = null;
    }

    void deleteNode(int val) {
        root = deleteRecursive(root, val);
    }

    Node deleteRecursive(Node root, int val) {
        if (root == null) {
            return root;
        }

        if (val < root.val) {
            root.left = deleteRecursive(root.left, val);
        } else if (val > root.val) {
            root.right = deleteRecursive(root.right, val);
        } else {
            // 找到要刪除的節點

            // 判斷是 Leaf？擁有一個子節點的節點？
            if (root.left == null) {
                return root.right;
            } else if (root.right == null) {
                return root.left;
            }

            // 擁有兩個子節點的節點
            // 製作 Inorder Successor
            root.val = minValue(root.right);
            // 刪除 Inorder Successor
            root.right = deleteRecursive(root.right, root.val);
        }

        return root;
    }

    int minValue(Node root) {
        int minValue = root.val;

        while (root.left != null) {
            minValue = root.left.val;
            root = root.left;
        }

        return minValue;
    }

    void insertNode(int val) {
        root = insertRecursive(root, val);
    }

    Node insertRecursive(Node root, int val) {
        if (root == null) {
            root = new Node(val);
            return root;
        }

        if (val < root.val) {
            root.left = insertRecursive(root.left, val);
        } else if (val > root.val) {
            root.right = insertRecursive(root.right, val);
        }

        return root;
    }

    void inorder() {
        inorderRecursive(root);
    }

    void inorderRecursive(Node root) {
        if (root != null) {
            inorderRecursive(root.left);
            System.out.println(root.val);
            inorderRecursive(root.right);
        }
    }

    public static void main(String[] args) {
        BinarySearchTree tree = new BinarySearchTree();

        tree.insertNode(50);
        tree.insertNode(30);
        tree.insertNode(20);
        tree.insertNode(40);
        tree.insertNode(70);
        tree.insertNode(60);
        tree.insertNode(80);

        System.out.println("Inorder traversal of the given tree");
        tree.inorder();

        System.out.println("\nDelete 20");
        tree.deleteNode(20);
        System.out.println("Inorder traversal of the modified tree");
        tree.inorder();

        System.out.println("\nDelete 30");
        tree.deleteNode(30);
        System.out.println("Inorder traversal of the modified tree");
        tree.inorder();

        System.out.println("\nDelete 50");
        tree.deleteNode(50);
        System.out.println("Inorder traversal of the modified tree");
        tree.inorder();
    }
}

用 C 實作

#include <stdio.h>
#include <stdlib.h>

struct Node
{
    int val;
    struct Node *left, *right;
};

struct Node *new_node(int key)
{
    struct Node *temp = (struct Node *)malloc(sizeof(struct Node));
    temp->val = key;
    temp->left = NULL;
    temp->right = NULL;
    return temp;
}

void inorder(struct Node *root)
{
    if (root != NULL)
    {
        inorder(root->left);
        printf("%d\n", root->val);
        inorder(root->right);
    }
}

struct Node *insert_node(struct Node *root, int key)
{
    if (root == NULL)
    {
        return new_node(key);
    }

    if (key < root->val)
    {
        root->left = insert_node(root->left, key);
    }
    else if (key > root->val)
    {
        root->right = insert_node(root->right, key);
    }

    return root;
}

struct Node *min_value_node(struct Node *root)
{
    struct Node *curent = root;

    while (curent && curent->left != NULL)
    {
        curent = curent->left;
    }

    return curent;
}

struct Node *delete_node(struct Node *root, int val)
{
    if (root == NULL)
    {
        return root;
    }

    if (val < root->val)
    {
        root->left = delete_node(root->left, val);
    }
    else if (val > root->val)
    {
        root->right = delete_node(root->right, val);
    }
    else
    {
        // 找到要刪除的節點

        // 判斷是 Leaf？擁有一個子節點的節點？
        if (root->left == NULL)
        {
            struct Node *temp = root->right;
            free(root);
            return temp;
        }
        else if (root->right == NULL)
        {
            struct Node *temp = root->left;
            free(root);
            return temp;
        }

        // 擁有兩個子節點的節點
        // 製作 Inorder Successor
        struct Node *temp = min_value_node(root->right);
        root->val = temp->val;
        // 刪除 Inorder Successor
        root->right = delete_node(root->right, temp->val);
    }

    return root;
}

int main(int argc, char const *argv[])
{
    struct Node *root = NULL;
    root = insert_node(root, 50);
    insert_node(root, 30);
    insert_node(root, 20);
    insert_node(root, 40);
    insert_node(root, 70);
    insert_node(root, 60);
    insert_node(root, 80);

    printf("Inorder traversal of the given tree \n");
    inorder(root);

    printf("\nDelete 20\n");
    root = delete_node(root, 20);
    printf("Inorder traversal of the modified tree \n");
    inorder(root);

    printf("\nDelete 30\n");
    root = delete_node(root, 30);
    printf("Inorder traversal of the modified tree \n");
    inorder(root);

    printf("\nDelete 50\n");
    root = delete_node(root, 50);
    printf("Inorder traversal of the modified tree \n");
    inorder(root);

    return 0;
}

刷題：1382. Balance a Binary Search Tree

題目

Given a binary search tree, return a balanced binary search tree with the same node values.

A binary search tree is balanced if and only if the depth of the two subtrees of every node never differ by more than 1.

If there is more than one answer, return any of them.

Constraints:

The number of nodes in the tree is between 1 and 10^4.
The tree nodes will have distinct values between 1 and 10^5.

Hint 1
Convert the tree to a sorted array using an in-order traversal.

Hint 2
Construct a new balanced tree from the sorted array recursively.

思考

提示很清楚，先用 inorder 取得 sorted array，再將其轉換成 BST 就完成了。

解題

JS

/**
 * @type {TreeNode[]}
 */
let output = [];

/**
 * @param {TreeNode} root
 */
const inorder = (root) => {
  if (root == null) {
    return;
  }

  inorder(root.left);
  output.push(root);
  inorder(root.right);
};

/**
 * @param {number} start
 * @param {number} end
 */
const balanced = (start, end) => {
  if (start > end) {
    return null;
  }

  let mid = (start + end) >> 1;
  let node = output[mid];
  node.left = balanced(start, mid - 1);
  node.right = balanced(mid + 1, end);
  return node;
};

/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
const balanceBST = (root) => {
  if (root == null) {
    return null;
  }

  output = [];
  inorder(root);
  return balanced(0, output.length - 1);
};

Java

class Solution {
    List<TreeNode> list = new ArrayList<>();

    void inorder(TreeNode root) {
        if (root == null) {
            return;
        }

        inorder(root.left);
        list.add(root);
        inorder(root.right);
    }

    TreeNode balanced(int start, int end) {
        if (start > end) {
            return null;
        }

        int mid = (start + end) >> 1;
        TreeNode node = list.get(mid);
        node.left = balanced(start, mid - 1);
        node.right = balanced(mid + 1, end);
        return node;
    }

    public TreeNode balanceBST(TreeNode root) {
        if (root == null) {
            return null;
        }

        inorder(root);
        return balanced(0, list.size() - 1);
    }
}

C

void inorder_to_count_nodes(struct TreeNode *root, int *count)
{
    if (root == NULL)
    {
        return;
    }

    inorder_to_count_nodes(root->left, count);
    (*count)++;
    inorder_to_count_nodes(root->right, count);
}

void inorder_to_create_output(struct TreeNode *root, struct TreeNode **output, int *index)
{
    if (root == NULL)
    {
        return;
    }

    inorder_to_create_output(root->left, output, index);
    output[(*index)++] = root;
    inorder_to_create_output(root->right, output, index);
}

struct TreeNode *balanced(struct TreeNode **output, int start, int end)
{
    if (start > end)
    {
        return NULL;
    }

    int mid = (start + end) >> 1;
    struct TreeNode *node = output[mid];
    node->left = balanced(output, start, mid - 1);
    node->right = balanced(output, mid + 1, end);
    return node;
}

struct TreeNode *balanceBST(struct TreeNode *root)
{
    int count = 0;
    inorder_to_count_nodes(root, &count);

    struct TreeNode **output = (struct TreeNode **)malloc(count * sizeof(struct TreeNode *));
    int index = 0;
    inorder_to_create_output(root, output, &index);

    root = balanced(output, 0, count - 1);
    free(output);
    return root;
}

看法

最麻煩的是 C，在於 C 沒有動態 Array，必須先計算全部有幾個節點後，再產生正確大小的Array。
有了排序過的Array、Array長度就可以利用 Recursive 將Array轉換成 BST。

結論

如果遇到 Tree 的問題，有很大的機率會運用到 BST 的概念。再來，BST 本身有過度傾斜的問題，後續衍生出不同的修改，例如 AVL、Red-Black Tree 等等，都是為了解決這問題而有不同的嘗試。

倒是我在寫 Leetcode 時，找一下網路上的討論，發現大多用 C++ 處理，想一想也對，C++ 支援物件導向、可以使用 Pointer，在實作上的難度會比 C 低許多。